class Solution {
  unsigned long long lcm(unsigned long long a, unsigned long long b) {
    unsigned long long final = a * b;
    if (a < b) {
      unsigned long long tmp = a;
      a = b;
      b = tmp;
    }
    while (b != 0) {
      unsigned long long tmp = a % b;
      a = b;
      b = tmp;
    }
    return final / a;
  }
  unsigned long long lcmAB, lcmAC, lcmBC, lcmABC;
  unsigned long long nUnderIt(long long num, long long a, long long b,
                              long long c) {
    return (num / a + num / b + num / c) -
           (num / lcmAB + num / lcmAC + num / lcmBC) + num / lcmABC;
  }

public:
  int nthUglyNumber(int n, int a, int b, int c) {
    lcmAB = lcm(a, b);
    lcmAC = lcm(a, c);
    lcmBC = lcm(b, c);
    lcmABC = lcm(lcmAB, c);
    unsigned long long left = 1, right = 2e9;
    while (left <= right) {
      unsigned long long mid = (left + right) >> 1;
      if (nUnderIt(mid, a, b, c) < n) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
};
